package com.ruoyi.learn.java.algorithm.searching;

/**
 * AVL 树 (自平衡二叉搜索树) 的 Java 实现
 * 通过旋转操作维持平衡，保证 O(log n) 的查找、插入、删除时间复杂度。
 * @param <T> 可比较的泛型类型
 */
public class AVLTree<T extends Comparable<T>> {

    // 树的根节点
    private Node root;

    // 节点内部类，包含数据、左右孩子指针和高度
    private class Node {
        T data;
        Node left;
        Node right;
        int height; // 节点的高度

        public Node(T data) {
            this.data = data;
            this.left = null;
            this.right = null;
            this.height = 1; // 新节点初始高度为 1
        }
    }

    // ------------------- 构造函数 -------------------
    public AVLTree() {
        this.root = null;
    }

    // ------------------- 辅助方法 -------------------

    // 获取节点的高度，空节点高度为 0
    private int height(Node node) {
        return node == null ? 0 : node.height;
    }

    // 计算节点的平衡因子
    private int getBalanceFactor(Node node) {
        return node == null ? 0 : height(node.left) - height(node.right);
    }

    // 更新节点的高度
    private void updateHeight(Node node) {
        if (node != null) {
            node.height = 1 + Math.max(height(node.left), height(node.right));
        }
    }

    // ------------------- 旋转操作 -------------------

    /**
     * 右旋转 (Right Rotation)
     * 用于处理 Left-Left 情况
     *       y               x
     *      / \             / \
     *     x   T3   -->    T1  y
     *    / \                 / \
     *   T1  T2              T2  T3
     */
    private Node rotateRight(Node y) {
        Node x = y.left;
        Node T2 = x.right;

        // 执行旋转
        x.right = y;
        y.left = T2;

        // 更新高度 (先更新 y，再更新 x，因为 x 是 y 的父节点)
        updateHeight(y);
        updateHeight(x);

        return x; // 新的子树根节点
    }

    /**
     * 左旋转 (Left Rotation)
     * 用于处理 Right-Right 情况
     *       x               y
     *      / \             / \
     *     T1  y    -->    x   T3
     *        / \         / \
     *       T2  T3      T1  T2
     */
    private Node rotateLeft(Node x) {
        Node y = x.right;
        Node T2 = y.left;

        // 执行旋转
        y.left = x;
        x.right = T2;

        // 更新高度 (先更新 x，再更新 y)
        updateHeight(x);
        updateHeight(y);

        return y; // 新的子树根节点
    }

    // ------------------- 核心操作 -------------------

    /**
     * 插入一个元素到 AVL 树
     * @param data 要插入的数据
     */
    public void insert(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Cannot insert null data");
        }
        root = insertRecursive(root, data);
    }

    // 递归插入辅助方法
    private Node insertRecursive(Node node, T data) {
        // 1. 执行标准 BST 插入
        if (node == null) {
            return new Node(data);
        }

        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            node.left = insertRecursive(node.left, data);
        } else if (compareResult > 0) {
            node.right = insertRecursive(node.right, data);
        } else {
            // 相等，通常不允许重复，直接返回 (可按需修改)
            return node;
        }

        // 2. 更新当前节点的高度
        updateHeight(node);

        // 3. 获取平衡因子
        int balance = getBalanceFactor(node);

        // 4. 如果节点不平衡，进行旋转操作

        // Left-Left Case
        if (balance > 1 && data.compareTo(node.left.data) < 0) {
            System.out.println("Left-Left Case");
            return rotateRight(node);
        }

        // Right-Right Case
        if (balance < -1 && data.compareTo(node.right.data) > 0) {
            System.out.println("Right-Right Case");
            return rotateLeft(node);
        }

        // Left-Right Case
        if (balance > 1 && data.compareTo(node.left.data) > 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }

        // Right-Left Case
        if (balance < -1 && data.compareTo(node.right.data) < 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        // 树已平衡，返回节点
        return node;
    }

    /**
     * 删除 BST 中的某个元素
     * @param data 要删除的数据
     */
    public void delete(T data) {
        if (data == null) {
            throw new IllegalArgumentException("Cannot delete null data");
        }
        root = deleteRecursive(root, data);
    }

    // 递归删除辅助方法
    private Node deleteRecursive(Node node, T data) {
        // 1. 执行标准 BST 删除
        if (node == null) {
            return node; // 数据不存在
        }

        int compareResult = data.compareTo(node.data);
        if (compareResult < 0) {
            node.left = deleteRecursive(node.left, data);
        } else if (compareResult > 0) {
            node.right = deleteRecursive(node.right, data);
        } else {
            // 找到要删除的节点
            // 情况 1: 没有或只有一个孩子
            if (node.left == null) {
                return node.right;
            } else if (node.right == null) {
                return node.left;
            }

            // 情况 2: 有两个孩子
            // 找到中序后继 (右子树的最小值)
            node.data = findMin(node.right).data;
            // 删除中序后继
            node.right = deleteRecursive(node.right, node.data);
        }

        // 2. 更新当前节点的高度
        updateHeight(node);

        // 3. 获取平衡因子
        int balance = getBalanceFactor(node);

        // 4. 如果节点不平衡，进行旋转操作

        // Left-Left Case
        if (balance > 1 && getBalanceFactor(node.left) >= 0) {
            return rotateRight(node);
        }

        // Left-Right Case
        if (balance > 1 && getBalanceFactor(node.left) < 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }

        // Right-Right Case
        if (balance < -1 && getBalanceFactor(node.right) <= 0) {
            return rotateLeft(node);
        }

        // Right-Left Case
        if (balance < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rotateRight(node.right);
            return rotateLeft(node);
        }

        return node;
    }

    /**
     * 查找 AVL 树中是否存在某个元素
     * @param data 要查找的数据
     * @return 如果找到返回 true，否则返回 false
     */
    public boolean search(T data) {
        if (data == null) {
            return false;
        }
        return searchRecursive(root, data);
    }

    private boolean searchRecursive(Node node, T data) {
        if (node == null) {
            return false;
        }
        int compareResult = data.compareTo(node.data);
        if (compareResult == 0) {
            return true;
        } else if (compareResult < 0) {
            return searchRecursive(node.left, data);
        } else {
            return searchRecursive(node.right, data);
        }
    }

    /**
     * 查找 AVL 树中的最小值
     * @return 最小值，如果树为空则返回 null
     */
    public T findMin() {
        if (root == null) {
            return null;
        }
        return findMin(root).data;
    }

    private Node findMin(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 查找 AVL 树中的最大值
     * @return 最大值，如果树为空则返回 null
     */
    public T findMax() {
        if (root == null) {
            return null;
        }
        return findMax(root).data;
    }

    private Node findMax(Node node) {
        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    // ------------------- 遍历操作 -------------------

    /**
     * 中序遍历
     */
    public void inOrderTraversal() {
        System.out.print("In-order: ");
        inOrderRecursive(root);
        System.out.println();
    }

    private void inOrderRecursive(Node node) {
        if (node != null) {
            inOrderRecursive(node.left);
            System.out.print(node.data + " ");
            inOrderRecursive(node.right);
        }
    }

    /**
     * 前序遍历
     */
    public void preOrderTraversal() {
        System.out.print("Pre-order: ");
        preOrderRecursive(root);
        System.out.println();
    }

    private void preOrderRecursive(Node node) {
        if (node != null) {
            System.out.print(node.data + " ");
            preOrderRecursive(node.left);
            preOrderRecursive(node.right);
        }
    }

    // ------------------- 辅助方法 -------------------

    public boolean isEmpty() {
        return root == null;
    }

    public int height() {
        return height(root);
    }

    public void clear() {
        root = null;
    }

    // ------------------- 主函数用于测试 -------------------
    public static void main(String[] args) {
        AVLTree<Integer> avl = new AVLTree<>();

        // 插入导致不平衡的序列
        int[] values = {10, 20, 30, 40, 50, 25}; // 插入 30 时会触发 Left-Left 旋转
        System.out.println("Inserting values: ");
        for (int val : values) {
            System.out.print(val + " ");
            avl.insert(val);
        }
        System.out.println();

        avl.inOrderTraversal();  // 应该有序
        avl.preOrderTraversal(); // 展示树的结构

        System.out.println("Search 25: " + avl.search(25)); // true
        System.out.println("Search 100: " + avl.search(100)); // false

        System.out.println("Min: " + avl.findMin()); // 10
        System.out.println("Max: " + avl.findMax()); // 50

        System.out.println("Height: " + avl.height()); // 应该较小

        // 删除
        System.out.println("Deleting 30");
        avl.delete(30);
        avl.inOrderTraversal();
        avl.preOrderTraversal();
        System.out.println("Height after deletion: " + avl.height());
    }
}
